﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Demo.Framework.Algorithms.UnionFind
{
    /*Aim - To find if two objects in a network is connected
     * The objects can be stored in an array from 0 to N-1
     * We can view the network consisting of different connection groups
     * with each connection group having a set of connected objects
     * Union(p,q) = Set all elements in p's connected group to q.
     * P's connected group => array[i] = array[p]
     * IsConnected(p,q) = array[p] = array[q] 
     * Advantage - Find is quick
     * Disadvantage - Union is complex
     * Note - We cannot accept a solution with O(N2) as it is not scalable
     */

    class QuickFind
    {
        private int[] _array;
        private int _count = 0;

        public QuickFind(int N)
        {
            _count = N;
            _array = new int[_count];

            for (int i = 0; i < _count; i++)
            {
                _array[i] = i;
            }
        }

        /// <summary>
        /// Time Complexity - O(1)
        /// </summary>
        /// <param name="p"></param>
        /// <param name="q"></param>
        /// <returns></returns>
        public bool IsConnected(int p, int q)
        {
            return _array[p] == _array[q];
        }

        /// <summary>
        /// Time Complexity - O(N2)
        /// </summary>
        /// <param name="p"></param>
        /// <param name="q"></param>
        /// <returns></returns>
        public bool Union(int p, int q)
        {
            try
            {
                for (int i = 0; i < _count; i++)
                {
                    if (_array[i] == _array[p])
                    {
                        _array[i] = _array[q];
                    }
                }
                return true;
            }
            catch (Exception)
            {                
                return false;
            }
        }

    }
}
